1. Field
This disclosure generally relates to a computing environment. More particularly, the disclosure relates to data gathering.
2. General Background
The computer set data structure has three operations: Add( ) Remove( ) and some form of accessor to read the contents of the set. Typical sets access the contents of the set approximately ninety percent of the time, perform Add( ) approximately nine percent of the time, and perform Remove( ) approximately one percent of the time. Thus, most implementations are optimized for these scenarios. In particular, most implementations are optimized around read-access being fast.
However, applications also often have to record information for use in unusual situations. An example is information that will only be utilized in the case of debugging, but cannot be reacquired later and thus has to be saved. Another example is information that will only be utilized in an infrequent clean-up activity. Any of these situations share the property that they frequently perform Add( ) and Remove( ) but rarely ever access the contents of the set. Such a set is referred to as an Add-Heavy Set. The Add( ) and Remove( ) operations have to be efficient and highly performant, but the accessor function performance is nearly irrelevant in such situations.
The set has to be specifically designed to address these concerns when multi-core systems with many threads running are involved. In these situations, typical implementations may lock or otherwise have slower implementations of Add( ) in order to keep accessing the set wait-free. This tradeoff is not beneficial for an Add-Heavy set.
Wait-free concurrent set implementations, which are wait-free for all operations, involve special synchronization primitives for Add( ) and Remove( ) such as Compare-and-Swap on X86. These instructions have to go to main memory and are very slow compared with normal instructions which at most access the processor's Level-1 cache.